package cn.zifangsky.dp.questions;

import org.junit.Test;

import java.util.Arrays;

/**
 * 最长递增子序列
 *
 * <p>【题目】</p>
 * <p>给定数组arr，返回arr的最长递增子序列。</p>
 * <p>【举例】</p>
 * <p>arr=[2，1，5，3，6，4，8，9，7]，返回的最长递增子序列为[1，3，4，8，9]。</p>
 *
 * @author zifangsky
 * @date 2020/5/29
 * @since 1.0.0
 */
public class Problem_007_LongestIncreasingSubsequence {

    /**
     * 测试代码
     */
    @Test
    public void testMethods(){
        int[] arr = {2, 1, 5, 3, 6, 4, 8, 9, 7};

        //1. 测试方法一
        int[] lis = solution1(arr);
        System.out.println(Arrays.toString(lis));
    }

    /**
     * 解法一
     * <ol>
     *     <li>生成长度为N的数组dp，dp[i]表示在以arr[i]这个数结尾的情况下，arr[0..i]中的最大递增子序列长度；</li>
     *     <li>对第一个数arr[0]来说，令dp[0]=1，接下来从左到右依次算出以每个位置的数结尾的情况下，最长递增子序列长度；</li>
     *     <li>假设计算到位置i，求以arr[i]结尾情况下的最长递增子序列长度，即dp[i]。如果最长递增子序列以arr[i]结尾，
     *         那么在arr[0..i-1]中所有比arr[i]小的数都可以作为倒数第二个数。在这么多倒数第二个数的选择中，
     *         以哪个数结尾的最大递增子序列更大，就选哪个数作为倒数第二个数，所以 dp[i]=max{dp[j]+1（0<=j<i，arr[j]<arr[i]）}。
     *     </li>
     * </ol>
     *
     * @param arr 数组
     */
    private int[] solution1(int[] arr){
        if(arr == null || arr.length < 1){
            return null;
        }

        //1. 求dp
        int[] dp = this.getDP1(arr);

        //2. 计算最长递增子序列
        return this.getLongestIncreasingSubsequence(arr, dp);
    }


    private int[] getDP1(int[] arr){
        //定义dp数组
        int[] dp = new int[arr.length];

        //求dp
        for(int i = 0; i < arr.length; i++){
            //默认认为以arr[i]结尾的最长递增子序列只包含arr[i]
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

        }

        return dp;
    }

    /**
     * LIS
     */
    private int[] getLongestIncreasingSubsequence(int[] arr, int[] dp){
        //1. dp数组中值最大的位置代表“最长递增子序列”的最后一个数
        int length = 0;
        int index = 0;
        for(int i = 0; i < dp.length; i++){
            if(dp[i] > length){
                length = dp[i];
                index = i;
            }
        }

        //2. 可以推测：“最长递增子序列”的倒数第二个数在0 ~ index-1之间，且dp[j] = dp[index]-1，倒数第三个数可以以此类推
        int[] result = new int[length];
        result[--length] = arr[index];

        for(int j = (index - 1); j >= 0; j--){
            if(arr[j] < arr[index] && (dp[j] == dp[index] - 1)){
                result[--length] = arr[j];
                index = j;
            }
        }

        //3. 返回结果
        return result;
    }

}
